\section{Proofs}

\subsection{Simplified Lifting Lemma}

The following lemma is a simplified
version of the Lifting Lemma stated in~\cite{XavierCampelo11}.

\begin{lemma}
Let $U \subseteq V$, $\beta \in \mathbb{R}$ and $\pi_v \in \mathbb{R}$, for all
$v \in U$, such that $\sum_{v \in U} \pi_v x_v \leq \beta$ is a valid inequality
for $STAB(G)$. If $c^\top x - d \leq 0$, $c,x \in \mathbb{R}^n$ and $d \in
\mathbb{R}$, is a valid inequality for $F=\{ x \in STAB(G) \mid \sum_{v \in U} \pi_v x_v = \beta \}$, then
\begin{equation}
(c^\top x - d) - \lambda\left(\sum_{v \in U}
\pi_v x_v - \beta \right) \leq 0,
\label{eq:lifted}
\end{equation}
with 
\begin{equation}
\lambda \leq \min \left\{ \frac{c^\top x - d}{\sum_{v \in U}
\pi_v x_v - \beta} \mid x \in \mathcal S, \sum_{v \in U}
\pi_v x_v < \beta \right\},
\label{eq:lambda}
\end{equation}
is a valid inequality for $STAB(G)$. In addition, if $\sum_{v \in U} \pi_v x_v
\leq \beta$ and $c^\top x - d \leq 0$ are facet-defining for $STAB(G)$ and $F$, respectively,
then~\eqref{eq:lifted} is facet-defining for $STAB(G)$.
\label{lem:lifting}
\end{lemma}


\subsection{Strengthened lifting procedure}

Let $G_0 := G$, $F_0 := STAB(G)$, and $W_1, \ldots, W_r$ be distinct subsets
of vertices with the following property: for every $t \in \{ 1, \ldots, r \}$,
$W_1, \ldots, W_t$ are cliques of $G_{t-1}$ and $G_t = (V, E_t)$ stands for
the projected graph $G_{t-1} \mid W_t$. Let also
\[
F_t := \{ x \in F_{t-1} \mid x_{W_t} = 1 \} = \{ x \in
STAB(G) \mid x_{W_j} = 1, j = 1, \ldots, t \}.
\]
Clearly, the integral elements of $F_t$ are stable sets of $G$. A property
of the clique projection operation is that they are also stable sets of
$G_t$. Define $N_G(v)$ as the neighborhood of $v$ in graph $G$.

\begin{lemma}
$F_t \subseteq STAB(G_t)$, for all $t \in \{ 0, \ldots, r \}$.
\label{lem:FtSTABGt}
\end{lemma}

\begin{proof}
% If $F_t = \emptyset$, then there is nothing to prove. Otherwise, we use
% induction on $t$ to show that $F_t \cap \mathcal S(G) \subseteq STAB(G_t) \cap
% \mathcal S(G)$. For $t = 1$, let $x \in F_1 \cap \mathcal S(G)$ ($x$ is an integer
% point in $F_1$) and $uv \in E_1$. By definition of $x$, there exists $z \in W_1$
% such that $x_z = 1$. It follows that $\{ uz, vz \} \cap E \neq \emptyset$
% because $W_1 \subseteq N(u) \cup N(v)$ by definition of clique projection. We conclude that $x_u = 0$ or $x_v = 0$ and, consequently,
% $x$ corresponds to a stable set of $G_1$. 
We use induction on $t$ to show that $F_t \cap \mathcal S(G) \subseteq STAB(G_t)
\cap \mathcal S(G)$. The basis $t = 0$ is trivial. For $t \geq 1$, $F_t
\subseteq F_{t-1}$, by definition, and $F_{t-1} \subseteq STAB(G_{t-1})$, by the induction
hypothesis. We show that $x \in (STAB(G_{t-1}) \setminus STAB(G_t)) \cap
\mathcal S(G)$ implies $x \not\in F_t$. For such an $x$, there is $uv \in E_t
\setminus E_{t-1}$ such that $x_{\{ u \}} = x_{\{ v \}} = 1$. By definition of
clique projection, $W_t \subseteq N(u) \cup N(v)$. Hence, $\{ uz, vz \} \cap E[G_{t-1}]
\neq \emptyset$ holds for every $z \in W_t$, leading to $x_{W_t} = 0$.
\end{proof}

By definition, $x_{W_t} \leq 1$ is valid for $STAB(G_{t-1})$. The previous lemma
implies that it is also valid for the stable sets of $G$ that cover $W_1, \ldots, W_{t-1}$.

\begin{corollary}
$x_{W_t} \leq 1$ is valid for $F_{t-1}$.
\label{cor:WtvalidFt1}
\end{corollary}

% \begin{proof}
% Let $x \in F_{t-1} \cap S(G)$ and $u, v \in W_t$. If $uv \in E$, then
% $x_{\{u,v\}} \leq 1$ since $x \in STAB(G)$. Otherwise, $uv \in E_t$ means that there is $\ell \in \{
% 1, \ldots, t-1 \}$ such that $W_\ell \subseteq N_{G_{\ell-1}}(u) \cup
% N_{G_{\ell-1}}(v)$. Hence, it follows from $x_{W_\ell} = 1$ that $x_{\{u\}} =
% 0$ or $x_{\{v\}} = 0$.
% \end{proof}

Our strengthened lifting procedure, stated in Lemma~\ref{lem:stlifting}, is as
follows.

\begin{lemma}
Let $c^\top x - d \leq 0$, $c,x \in \mathbb{R}^n$ and $d \in
\mathbb{R}$, be a valid inequality for $STAB(G_r)$.
Then, $f_t(x) \leq d$ is valid for $F_t$, where, for $t \in \{ 0,
\ldots, r \}$, 
\[
f_t(x) = c^\top x + \sum_{\ell=t+1}^r \phi_\ell (x_{W_\ell} - 1),
\]
$\mathcal S_t = \mathcal S(G) \cap F_t$, and
\[
\phi_\ell = \max \Big\{ \{ 0 \} \cup \big\{ f_\ell(x) - d \mid
x \in \mathcal S_{\ell-1}, x_{W_\ell} = 0 \big\} \Big\}.
\]
\end{lemma}

\begin{proof}
We show that $f_t(x) \leq d$ is valid for $F_t$ by induction on $t$. For $t
= r$, the result follows since $f_r(x) = c^\top x \leq d$ is valid for
$STAB(G_r)$ and $F_r \subseteq STAB(G_r)$ by Lemma~\ref{lem:FtSTABGt}.
For $t < r$, by induction hypothesis, $f_{t+1}(x) \leq d$ is valid for
$F_{t+1} = \{ x \in F_t \mid x_{W_{t+1}} = 1 \}$. Applying the inequality
construction, we get $\phi_{t+1} = 0$, if $\{ x \in \mathcal S_t \mid
x_{W_{t+1}} = 0 \} = \emptyset$, or
\[
\phi_{t+1} = \max \left\{ c^\top x + \sum_{i=t+2}^r \lambda_i (x_{W_i} - 1)
\mid \begin{array}{l} x \in \mathcal S_t, \\ x_{W_{t+1}} = 0 \end{array} \right\} -
d.
\]
We now apply the Lemma~\ref{lem:lifting}, considering that $x_{W_{t+1}} \leq 1$
is valid for $STAB(G_t)$ (which means, by Lemma~\ref{lem:FtSTABGt}, that $x_{W_{t+1}}
\leq 1$ is valid for $F_t$) and $f_{t+1}(x) \leq d$ is valid for
$F_{t+1}$, and then obtain that $f_t(x)
\leq d$ is valid for $F_t$.
\end{proof}

\subsection{Sufficient conditions for faceteness}

The sufficient conditions we state below are slightly weaker than those
in~\cite{XavierCampelo11}. Consider the subsets $W_1, \ldots, W_{r+1}$. We show
in this section that if there exists $k > 0$ such that the
following conditions hold, for all $t \in \{ 1, \ldots, r \}$:
\begin{enumerate}[label=(\Roman*),ref=\Roman*,series=conds]
  \item $|W_t| = k$ and the subgraph of $G_{t-1}$ induced by $\bigcup_{i=1}^t
  W_i$ is $k$-partite with vertex classes $V_t^1, \ldots, V_t^k$,
  \label{it:Wk}
  \item $T_t := (V_t, \mathcal W_t)$ is a $k$-uniform strong hypertree
  defined by $V_t := \bigcup_{i=1}^k V_t^i$ and $\mathcal W_t := \{ W_1,
  \ldots, W_t \}$,
  \label{it:Tt}
  \item for all $w \in V_t^0 := V \setminus V_t$, there exists $i \in \{ 1,
  \ldots, k \}$ such that $N_{G_{t-1}}(w) \cap V_t^i = \emptyset$,
  \label{it:vV0}
\end{enumerate}
then
\begin{enumerate}[label=(\emph{\roman*}),ref=\emph{\roman*},series=claims]
  \item $x_{W_t} \leq 1$ is facet defining for $F_{t-1}$.
  \label{it:Ft1}
\end{enumerate}
If, in addition to conditions~\eqref{it:Wk}--\eqref{it:Tt}, we
assume that
\begin{enumerate}[label=(\Roman*),ref=\Roman*,resume*=conds]
  \item for every $i \in \{ 1, \ldots, k-1 \}$ and $w \in V_r^0$ such that
  $N_{G_r}(w) \cap V_r^i \ne \emptyset$, one of the following holds: $v \in W_t \cap V_t^i$ is a
  neighbor of $w$ in $G$ or there exists $t' \in \{ 1, \ldots, r \}$ such that $W_t$ is a clique of
  $G_{t'-1}$, $W_t$ and $W_{t'}$ are adjacent in $T_r$, $v \not\in W_{t'}$,
  and $v' \in W_{t'} \cap V_r^i$ is a neighbor of $w$ in $G_{t'-1}$,
  \label{it:noclique}
  \item every $v \in V_t^k$ has no neighbors in $V_r^0$, {\em i.e.} $N_{G_r}(v)
  \cap V_r^0 = \emptyset$,
  \label{it:VkV0}
\end{enumerate}
then we prove that
\begin{enumerate}[label=(\emph{\roman*}),ref=\emph{\roman*},resume*=claims]
  \item $f_t(x) \leq 1$ is facet defining for $F_t$,
  \label{it:Ft}
\end{enumerate}
considering that $f_r(x) = x_{W_{r+1}}$ and $W_{r+1}$ is a maximal clique of
$G_r$ such that $W_{r+1} \cap V_r^k = \emptyset$. These conditions differ from
those in~\cite{XavierCampelo11} in two points. First, we do not ask for the
subsets $W_3, \ldots, W_r$ to be cliques in $G$. Second, we use clique
projection and we assume condition~\eqref{it:noclique} to impose appropriate false edges in
$G_{t'}$ instead of the auxiliary contracted graph defined
in~\cite{XavierCampelo11} to determine $W_{r+1}$.

\subsubsection{Proof of~\eqref{it:Ft1}}

The proof of~\eqref{it:Ft1} depends on the dimension of $F_t$, established
next, which in turn depends on conditions~\eqref{it:Wk}--\eqref{it:vV0}.

\begin{lemma}
If~\eqref{it:Wk} holds, then $|W_\ell \cap V^i_t| = 1$, for all $\ell
\in \{ 1, \ldots, t \}$ and $i \in \{ 1, \ldots, k \}$.
\label{lem:interWV}
\end{lemma}

\begin{proof}
Since $W_\ell$ is a clique and $V^i_t$ is a stable set, $|W_\ell \cap V^i_t|
\leq 1$. By condition~\eqref{it:Wk}, $|W_\ell|=k$ and there are at least $k$
stable sets intersecting $W_\ell$. Therefore, $|W_\ell \cap V^i_t| \geq 1$.
\end{proof}

\begin{lemma}[Adapted from Lemma 3.1 of~\cite{XavierCampelo11}]
If~\eqref{it:Wk}--\eqref{it:vV0} hold, then $dim(F_t) = n -
t$.
\label{lem:dimFt}
\end{lemma}

\begin{proof}
Because the incidence matrix of $T_t$ has rank $t$ due to
conditions~\eqref{it:Tt}, it follows that $dim(F_t) \leq n
- t$. To prove that $dim(F_t) \geq n - t$, we exhibit $n-t+1$ affinely independent vectors of
$F_t$. For this purpose, define $x^i$ to be
the incidence vector of $V_t^i$, for every $i \in \{1, \ldots, k\}$. Clearly,
$x^i \in STAB(G)$ and, by Lemma~\ref{lem:interWV}, $x^i_{W_\ell} = 1$ for all $\ell
\in \{ 1, \ldots, t \}$, which
means that $x^i \in F_t$. For every $v \in V_t^0$, define $y_v = x^i + e_v$ where $i \in \{1, \ldots, k\}$ is such that $v$ is not adjacent to any vertex in $V_t^i$, by
condition~\eqref{it:vV0}, and $e_v$ is the incidence vector of $\{ v \}$.
Again, it is easy to see that $y_v \in F_t$. The $|V_t^0| + k = n - (k + t - 1)
+ k = n - t + 1$ points $\{x^i\}^k_{i=1} \cup \{y_v\}_{v\in V_t^0}$ are affinely
independent.
\end{proof}

\begin{theorem}
If~\eqref{it:Wk}--\eqref{it:vV0} hold, then~\eqref{it:Ft1}
holds for all $t \in \{ 1, \ldots, r \}$.
\label{thm:condi}
\end{theorem}

\begin{proof}
By Lemma~\ref{lem:dimFt}, $dim(F_t) = dim(F_{t-1})-1$. Thus, by
Corollary~\ref{cor:WtvalidFt1}, $F_t = \{x \in F_{t-1} \mid x_{W_t} = 1\}$ is a
facet of $F_{t-1}$.
\end{proof}

A remark that can be done with respect to conditions~\eqref{it:Wk}--\eqref{it:vV0} is that they are sufficient for~\eqref{it:Ft} when $t < r$.

\begin{theorem}
If~\eqref{it:Wk}--\eqref{it:vV0} hold for all $t \in \{ 1,
\ldots, r \}$, $f_r(x) = x_{W_r}$, and $d = 1$, then~\eqref{it:Ft} holds for all
$t \in \{ 1, \ldots, r-1 \}$.
\label{thm:simplercondi}
\end{theorem}

\begin{proof}
By induction on $t$. For $t = r$, $x_{W_{r+1}} \leq 1$ is facet defining for
$F_r$ by~\eqref{it:Ft1}. For $t < r$, $x_{W_{t+1}} \leq 1$ is facet defining for
$F_t$ by~\eqref{it:Ft1} and $f_{t+1}(x)$ is facet defining for $F_{t+1} = \{ x \in F_t \mid x_{W_{t+1}} = 1 \}$ by induction hypothesis.
Thus, the result follows by Lemma~\ref{lem:lifting}.
\end{proof}

\subsubsection{Proof of~\eqref{it:Ft}}

Conditions~\eqref{it:Wk}--\eqref{it:Tt} imply the
following property of $G_r$ and the stable sets of $G$ that cover $W_1,
\ldots, W_r$.

\begin{lemma}[Adapted from Lemma 3.2 of~\cite{XavierCampelo11}]
If~\eqref{it:Wk}--\eqref{it:Tt} hold and $x \in F_t$, then $x_{\{
u \}} = x_{\{ v \}}$, for all $i \in \{ 1, \ldots, k \}$ and $\{ u, v \} \subseteq V_t^i$.
\label{lem:xuv}
\end{lemma}

\begin{proof}
Considering that conditions~\eqref{it:Wk}--\eqref{it:Tt} hold, let $W_{t_1},
\ldots, W_{t_q}$ be the strong hyperpath in $T_t$ connecting $u, v$. We
prove the result by induction on $q$. If $q = 2$, then $x_{W_{t_1}}
- x_{W_{t_2}} = x_{\{u\}} - x_{\{v\}} = 0$. Otherwise, $q > 2$. Let $w \in
W_{t_2} \setminus W_{t_1}$. Since $u \not\in W_{t_2}$, we
conclude that $w \in V_{t_2}^i$ by Lemma~\ref{lem:interWV}. Hence, $W_{t_1},
W_{t_2}$ is a strong hyperpath with 2 hyperedges connecting $u,w$, which gives $x_{\{ u \}} = x_{\{ w \}}$. Moreover, $W_{t_p}, \ldots,
W_{t_q}$, for $p = \max \{ j \mid w \in W_{t_j} \}$, is a strong hyperpath with less than $q$
hyperedges connecting two vertices of $V_t^i$. By inductive hypothesis,
$x_{\{ w \}} = x_{\{ v \}}$. Therefore, $x_{\{ u \}} = x_{\{ v \}}$.
\end{proof}

Differently from~\cite{XavierCampelo11}, we determine $W_{r+1}$ in $G_r$
(instead of defining an auxiliary graph). For this purpose, we use the
following property of $G_r$ due to
conditions~\eqref{it:Wk}--\eqref{it:Tt} and~\eqref{it:noclique}.

\begin{lemma}
Let $v \in V_t^i \cap W_t$, for some $i \in \{ 1, \ldots, k-1 \}$, and $w \in
V_r^0$ be such that $V_r^i \cap N_{G_r}(w) \ne \emptyset$.
If~\eqref{it:Wk}--\eqref{it:Tt} and~\eqref{it:noclique} hold, then $vw \in E_r$.
\label{lem:equalVi}
\end{lemma}

\begin{proof}
If $vw \in E$, then the lemma is trivially valid. Otherwise, by
condition~\eqref{it:noclique}, let $t' \in \{ 1, \ldots, r \}$ be such that
$W_t$ is a clique of $G_{t'-1}$, $W_t$ and $W_{t'}$ are adjacent in $T_r$
(considering conditions~\eqref{it:Wk}--\eqref{it:Tt}), $v \not\in W_{t'}$ and
$v' \in W_{t'} \cap V_r^i$ is a neighbor of $w$ in $G_{t'-1}$. In this situation, $W_{t'} \subseteq
N_{G_{t'-1}}(v) \cup N_{G_{t'-1}}(w)$ implies $vw \in E_{t'} \subseteq E_r$ by
the clique projection of $W_{t'}$.
\end{proof}

To show~\eqref{it:Ft}, we still need the following property of the subgraph of
$G_r$ induced by $V_r^0$ and a certain subset of vertices. Notation $\cong$ denotes
the affine isomorphism relation~\cite{XavierCampelo11}.

\begin{lemma}[Adapted from Lemma 3.3 of~\cite{XavierCampelo11}]
If \eqref{it:Wk}--\eqref{it:VkV0} hold for $t=r$, then
$F_r \cong STAB(G_r[V_r^0 \cup R])$ where $R \subseteq V$ is such that
$|R \cap V_r^i| = 1$, for all $i \in \{1, \ldots, k-1\}$, and $R \cap V_r^k
= \emptyset$.
\label{lem:cong}
\end{lemma}

\begin{proof}
In what follows, we denote by $v_i$ the unique vertex in $R \cap
V_r^i$, for all $i \in \{1, \ldots, k-1 \}$.
\begin{description}
\item[{$STAB(G_r[V_r^0 \cup R]) \to F_r$:}] Take a point in $y \in
STAB(G_r[V_r^0 \cup R])$. For each $u \in V$, set $x_u = y_u$ if $u \in
V_r^0$; $x_u = y_{v_i}$, if $u \in V_r^i$, $i \in \{1, \ldots, k-1 \}$; and $x_u
= 1 - \sum^{k-1}_{i=1} y_{v_i}$, if $u \in V_r^k$. We prove
that $x \in F_r$. First, to show that $x \in STAB(G)$, take $uw \in E$. If $u,w
\in V_r^0 \cup R$, then $x_u + x_w \leq 1$ trivially holds. If $u,w \in V_r$, then $x_u + x_w \leq 1$ because $\{ u, w \} \setminus V_r^i \ne
\emptyset$, for all $i \in \{1, \ldots, k \}$. Otherwise, assume without loss of
generality that $u \in V_r \setminus R$ and $w \in V_r^0 \setminus R$. It turns out
that $u \not\in V_r^k$ by condition~\eqref{it:VkV0}. Then, use
Lemma~\ref{lem:equalVi} to conclude that $v_iw \in E_r$ and, consequently,
$x_u + x_w \leq 1$. To show that $x_{W_\ell} = 1$, for $\ell \in \{ 1, \ldots, t
\}$, we use Lemma~\ref{lem:interWV} to write $x_{W_\ell} = \sum^{k-1}_{i=1} y_{v_i} + (1 -
\sum^{k-1}_{i=1} y_{v_i}) = 1$.
\item[{$F_r \to STAB(G_r[V_r^0 \cup R])$:}] Take $x \in F_r$. For each $v
\in V_r^0$, set $y_v = x_v$, and for each $i \in \{ 1, \ldots, k -1 \}$, set
$y_{v_i} = x_{v_i}$. This mapping is injective due to Lemma~\ref{lem:xuv}. Take
$vw \in E[V_r^0 \cup R]$.
It is straightforward to check that $y_v + y_w \leq 1$.
\end{description}
\end{proof}

Claim~\eqref{it:Ft} follows directly from Lemma~\ref{lem:cong} combined with the
Lifting Lemma.

\begin{theorem}
If \eqref{it:Wk}--\eqref{it:Tt} and~\eqref{it:noclique}--\eqref{it:VkV0} hold,
$f_r(x) = x_{W_{r+1}}$, and $W_{r+1}$ is a maximal clique of $G_r$ such that $W_{r+1} \cap V_r^k = \emptyset$,
then~\eqref{it:Ft} holds for all $t \in \{ 1, \ldots, r \}$.
\label{thm:condii}
\end{theorem}

\begin{proof}
By induction on $t$. For $t = r$, $x_{W_{r+1}} \leq 1$ is facet defining for
$STAB(G_r[V_r^0 \cup R])$, for every $R \subseteq V$ such that
$|R \cap V_r^i| = 1$, for all $i \in \{1, \ldots, k-1\}$, $R
\cap V_r^k = \emptyset$, and $W_{r+1} \subseteq R$. Such an
$R$ exists since $W_{r+1} \cap V_r^k = \emptyset$. Hence, by
Lemma~\ref{lem:cong}, $f_r(x) = x_{W_{r+1}} \leq 1$ is facet defining for $F_r$. For $t < r$,
$x_{W_{t+1}} \leq 1$ is facet defining for $F_t$ by~\eqref{it:Ft1} (notice
that~\eqref{it:VkV0} implies~\eqref{it:vV0} and therefore we can use
Theorem~\ref{thm:condi}) and $f_{t+1}(x)$ is facet defining for $F_{t+1} = \{ x \in F_t \mid x_{W_{t+1}} = 1 \}$ by induction hypothesis.
Thus, the result follows by Lemma~\ref{lem:lifting}.
\end{proof}

